package com.wangjie.doublepointer;

/**
 * @author jieshao
 * @date 2022/4/29 14:57
 */
public class Test11 {
    public static void main(String[] args) {
        ListNode t5 = new ListNode(5, null);
        ListNode t4 = new ListNode(4, t5);
        ListNode t3 = new ListNode(3, t4);
        ListNode t2 = new ListNode(2, t3);
        ListNode t1 = new ListNode(1, t2);
        System.out.println("反转前：");
        for (ListNode p = t1; p != null; p = p.next) {
            System.out.println(p.val);
        }

        ListNode head = reverseBetween(t1, 2, 4);

        System.out.println("反转后：");
        for (ListNode p = head; p != null; p = p.next) {
            System.out.println(p.val);
        }
    }

    // 后驱节点
    private static ListNode temp = null;

    /**
     * 反转链表的前 N 个节点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 记录第 n + 1 个节点
            temp = head.next;
            return head;
        }
        // 以 head.next 为起点，需要反转前 n - 1 个节点
        ListNode last = reverseN(head.next, n - 1);
        head.next.next = head;
        // 让反转之后的 head 节点和后驱节点连起来
        head.next = temp;
        return last;
    }

    /**
     * 反转链表的一部分
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            // 相当于反转前 n 个节点
            return reverseN(head, right);
        }
        // 前进到反转的起点，将其转化为反转前 n 个节点
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
}